package shuati.shua;

import java.util.Stack;

/**
 * @author : LdLtd
 * @Date : 2024/4/29
 * @Description:所有排序
 * 1）插入排序（直接插入排序、希尔排序）
 * 2）交换排序（冒泡排序、快速排序）
 * 3）选择排序（直接选择排序、堆排序）
 * 4）归并排序
 * 5）分配排序（基数排序）
 * 所需辅助空间最多：归并排序
 * 所需辅助空间最少：堆排序
 * 平均速度最快：快速排序
 * 不稳定：快速排序，希尔排序，堆排序
 */
public class AllSort {
    public static void main(String[] args) {
        int[] arr = new int[]{25, 15, 71, 34, 91};
        radixSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    /*冒泡排序
     * 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
     * 2.对每一对相邻的元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
     * 3.针对所有的元素重复以上的步骤，除了最后一个。
     * 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
     */
    public static void bubbleSort(int[] arr) {
        int i, j, t;
        for (i = 0; i < arr.length - 1; i++) {
            for (j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) { //这是升序，降序换符号
                    t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                }
            }
        }
    }

    /*快速排序
     * 1.从数列中挑出一个元素，称为"基准"（pivot），
     * 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆放在基准的后面（相同的数可以到任一边）。
     * 3.在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
     * 4.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
     * 5.递归到最底部的判断条件是数列的大小是零或一，这时数列显然有序。
     * 6.选择一个基准元素，通常选择第一个元素或者最后一个元素。
     * 7.通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。
     * 8.然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
     * 9.快速排序是不稳定的排序算法。
     * 10.快速排序的时间复杂度为O(nlogn)。
     * 11.快速排序的空间复杂度为O(logn)。
     * 12.快速排序是原地排序算法。
     * 13.快速排序是分治算法的典型应用。
     * 14.快速排序是处理大数据集最快的排序算法之一。
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //t作为基准数
            int i = left, j = right, t = arr[left];
            while (i != j) {
                //从右往左找比t小的数
                while (i < j && arr[j] >= t) {
                    j--;
                }
                //从左往右找比t大的数
                while (i < j && arr[i] <= t) {
                    i++;
                }
                //交换i和j的数
                if (i < j) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            //两指针相遇，交换基准数到相遇位置
            //此时t的位置已经确定，但i的位置不确定
            arr[left] = arr[i];
            arr[i] = t;
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }

    /*快速排序，栈实现
     * 1.将基准数的左右边界压栈
     * 2.出栈，找到基准数的位置，再次压栈
     * 3.重复2，直到栈为空
     * 4.栈的压栈顺序是先压右边界，再压左边界
     * 5.栈的出栈顺序是先出左边界，再出右边界
     * 6.栈的压栈和出栈是一一对应的
     */
    public static void quickSortStack(int[] arr, int left, int right) {
        Stack<Integer> stack = new Stack<>();
        stack.push(left);
        stack.push(right);
        while (!stack.isEmpty()) {
            int r = stack.pop();
            int l = stack.pop();
            if (l < r) {
                int i = l, j = r, t = arr[l];
                while (i != j) {
                    while (i < j && arr[j] >= t) {
                        j--;
                    }
                    while (i < j && arr[i] <= t) {
                        i++;
                    }
                    if (i < j) {
                        int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
                arr[l] = arr[i];
                arr[i] = t;
                stack.push(l);
                stack.push(i - 1);
                stack.push(i + 1);
                stack.push(r);
            }
        }
    }

    /*选择排序
     * 1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
     * 2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     * 3.重复第二步，直到所有元素均排序完毕。
     * 4.选择排序是不稳定的排序算法。
     * 5.选择排序的时间复杂度为O(n^2)。
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }

    }

    /*双指针优化选择排序
     * 1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
     * 2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     */
    public static void selectSort2(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int minIndex = left, maxIndex = right;
            //找到最小值和最大值的下标
            for (int i = left; i <= right; i++) {
                if (arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            //交换最小值和最大值
            if (minIndex != left) {
                int temp = arr[left];
                arr[left] = arr[minIndex];
                arr[minIndex] = temp;
            }
            //此时，left已经是最小值的下标，minIndex被交换到left
            //所以交换后的最大值的下标是minIndex
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            if (maxIndex != right) {
                int temp = arr[right];
                arr[right] = arr[maxIndex];
                arr[maxIndex] = temp;
            }
            left++;
            right--;
        }
    }
    /*插入排序
     * 1.从第一个元素开始，该元素可以认为已经被排序。
     * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描。
     * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置。
     * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
     * 5.将新元素插入到该位置后。
     * 6.重复步骤2~5。
     * 7.插入排序是稳定的排序算法。
     * 8.插入排序的时间复杂度为O(n^2)。
     * 9.插入排序的空间复杂度为O(1)。
     */

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

    /*归并排序
     * 1.把长度为n的输入序列分成两个长度为n/2的子序列。
     * 2.对这两个子序列分别采用归并排序。
     * 3.将两个排序好的子序列合并成一个最终的排序序列。
     * 4.归并排序是稳定的排序算法。
     * 5.归并排序的时间复杂度为O(nlogn)。
     * 6.归并排序的空间复杂度为O(n)。
     * 7.归并排序是分治算法的典型应用。
     */
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) >> 1;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (int l = 0; l < temp.length; l++) {
            arr[left + l] = temp[l];
        }
    }

    /*堆排序
     * 1.将待排序序列构造成一个大顶堆。
     * 2.此时，整个序列的最大值就是堆顶的根节点。
     * 3.将其与末尾元素进行交换，此时末尾就为最大值。
     * 4.然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
     * 5.如此反复执行，便能得到一个有序序列。
     * 6.堆排序是不稳定的排序算法。
     * 7.堆排序的时间复杂度为O(nlogn)。
     * 8.堆排序的空间复杂度为O(1)。
     * 9.堆排序是原地排序算法。
     * 10.堆排序是选择排序的一种。
     */
    public static void heapSort(int[] arr) {
        int n = arr.length;
        //构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, i, n);
        }
        //堆排序
        for (int i = n - 1; i > 0; i--) {
            //交换堆顶和最后一个元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //重新调整堆
            heapify(arr, 0, i);
        }
    }

    public static void heapify(int[] arr, int i, int n) {
        //下标从0开始，左孩子为2*i+1，右孩子为2*i+2
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;
        //找出三个节点中最大的节点
        if (left < n && arr[left] > arr[max]) {
            max = left;
        }
        if (right < n && arr[right] > arr[max]) {
            max = right;
        }
        //如果最大的节点不是根节点，交换根节点和最大节点
        if (max != i) {
            int temp = arr[i];
            arr[i] = arr[max];
            arr[max] = temp;
            heapify(arr, max, n);
        }
    }

    /*希尔排序
     * 1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1。
     * 2.按增量序列个数k，对序列进行k 趟排序。
     * 3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
     * 4.仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     * 5.希尔排序是不稳定的排序算法。
     * 6.希尔排序的时间复杂度为O(nlogn)。
     * 7.希尔排序的空间复杂度为O(1)。
     * 8.希尔排序是原地排序算法。
     * 9.希尔排序是插入排序的一种。
     */
    public static void shellSort(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int j = i;
                int temp = arr[j];
                //以gap为间隔进行插入排序
                while (j - gap >= 0 && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

    /*基数排序
     * 1.基数排序是按照低位先排序，然后收集；
     * 2.再按照高位排序，然后再收集；
     * 3.依次类推，直到最高位。
     * 4.有时候有些属性是有优先级顺序的，先按照低优先级排序，再按照高优先级排序。
     * 5.基数排序是稳定的排序算法。
     * 6.基数排序的时间复杂度为O(d(n+r))，其中r为基数，d为位数。
     * 如 25 15 71 34 91
     * 用一个0~9的桶，按个位数排序，得到 71 91 25 15 34
     * 再按十位数排序，得到 15 25 34 71 91
     * 　例如：要排序全部由小写字母组成的字符串，
     * 则基数就是26，就会用到26个单独的队列。如果对十进制数进行排序，则基数应该是10.
     */
    public static void radixSort(int[] arr) {
        int n = arr.length;
        int max = arr[0];
        //找出最大值
        for (int i = 1; i < n; i++) {
            max = Math.max(max, arr[i]);
        }
        //如对 25 15 71 34 91排序
        //初始位数为1
        int exp = 1;
        int[] temp = new int[n];
        //按位数进行排序
        while (max / exp > 0) {
            int[] count = new int[10];
            //统计每个数落在哪个桶里，并且统计每个桶的个数
            //则count[5]=2,count[4]=1,count[1]=2
            for (int i = 0; i < n; i++) {
                count[arr[i] / exp % 10]++;
            }
            //计算每个桶的右边界，即每个桶的最后一个元素的下标，方便后面排序放入原数组
            //则count[0]=0,count[1]=2,count[2]=2,count[3]=2,count[4]=3,count[5]=5,count[6]=5,count[7]=5,count[8]=5,count[9]=5
            for (int i = 1; i < 10; i++) {
                count[i] += count[i - 1];
            }
            //按位数排序
            for (int i = n - 1; i >= 0; i--) {
                //从后往前遍历，保证稳定性
                //count[arr[i] / exp % 10]是arr[i]的位置
                //如25/1%10=5,15/1%10=5,71/1%10=1,34/1%10=4,91/1%10=1
                //倒序遍历，所以25在第4个位置，15在第5个位置，71在第1个位置，34在第3个位置，91在第2个位置
                temp[--count[arr[i] / exp % 10]] = arr[i];
            }
            //将排序后的数组赋值给原数组
            for (int i = 0; i < n; i++) {
                arr[i] = temp[i];
            }
            //位数乘10
            exp *= 10;
        }
    }
    /*
    *计数排序
    * 1.计数排序是稳定的排序算法。
    * 2.计数排序的时间复杂度为O(n+r)，其中r为最大值。
    * 3.计数排序的空间复杂度为O(n+r)，其中r为最大值。
    * 4.计数排序是原地排序算法。
    * 5.计数排序是选择排序的一种。
    * 6.计数排序是桶排序的一种。
    * 7.计数排序的步骤：
    * 1.找出数组中的最大值max，创建一个长度为max+1的数组count，用于统计每个数字出现的次数。
    * 2.遍历数组，将每个数字出现的次数记录在count数组中。
    * 3.遍历count数组，将每个数字出现的次数累加到count数组中。
    * 4.遍历数组，将每个数字出现的次数记录在count数组中。
    * 5.构建排序后的数组，创建一个与原始数组长度相同的输出数组 output。
    * 然后，从后向前遍历原始数组（保证稳定），根据计数数组 count 中的值，
    * 将每个数字放到输出数组 output 中的正确位置。每放置一个数字后，将计数数组 count 中对应的值减 1。
    * 6.返回排序后的数组
    *
    * */
    public static void countSort(int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return; // 如果数组为空，直接返回
        }

        // 1. 找出数组中的最大值
        int max = arr[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(max, arr[i]);
        }
        // 2. 创建计数数组，长度为 max + 1，并初始化为 0
        int[] count = new int[max + 1];
        // 3. 统计每个数字出现的次数
        for (int i = 0; i < n; i++) {
            count[arr[i]]++;
        }
        // 4. 累加计数数组，确定每个数字的最终位置
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }
        // 5. 创建输出数组，用于存储排序后的结果
        int[] output = new int[n];
        // 6. 从后向前遍历原始数组，将元素放入输出数组的正确位置
        for (int i = n - 1; i >= 0; i--) {
            output[--count[arr[i]]] = arr[i]; // 将 arr[i] 放到正确的位置，并减少计数
        }
        // 7. 将排序后的结果复制回原始数组
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
        // 8. 打印排序后的数组
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
